package com.cencat.common.utils;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.beans.BeanUtils;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 树形结构工具类
 * 提供树形数据的构建、遍历、查找等功能
 * 
 * @author cencat
 * @since 2024-01-01
 */

public class TreeUtils {

    private static final Logger log = LoggerFactory.getLogger(TreeUtils.class);

    private TreeUtils() {
        // 私有构造函数，防止实例化
    }

    /**
     * 构建树形结构
     * 
     * @param list         数据列表
     * @param idExtractor  ID提取器
     * @param pidExtractor 父ID提取器
     * @param <T>          数据类型
     * @param <ID>         ID类型
     * @return 树形结构列表
     */
    public static <T extends TreeNode<ID>, ID> List<T> buildTree(List<T> list, 
                                                                 Function<T, ID> idExtractor, 
                                                                 Function<T, ID> pidExtractor) {
        return buildTree(list, idExtractor, pidExtractor, null);
    }

    /**
     * 构建树形结构（指定根节点ID）
     * 
     * @param list         数据列表
     * @param idExtractor  ID提取器
     * @param pidExtractor 父ID提取器
     * @param rootId       根节点ID
     * @param <T>          数据类型
     * @param <ID>         ID类型
     * @return 树形结构列表
     */
    public static <T extends TreeNode<ID>, ID> List<T> buildTree(List<T> list, 
                                                                 Function<T, ID> idExtractor, 
                                                                 Function<T, ID> pidExtractor, 
                                                                 ID rootId) {
        if (list == null || list.isEmpty()) {
            return new ArrayList<>();
        }

        // 创建ID到节点的映射
        Map<ID, T> nodeMap = list.stream()
                .collect(Collectors.toMap(idExtractor, Function.identity(), (existing, replacement) -> existing));

        // 构建父子关系
        List<T> rootNodes = new ArrayList<>();
        for (T node : list) {
            ID parentId = pidExtractor.apply(node);
            
            if (isRootNode(parentId, rootId)) {
                // 根节点
                rootNodes.add(node);
            } else {
                // 子节点
                T parent = nodeMap.get(parentId);
                if (parent != null) {
                    parent.addChild(node);
                }
            }
        }

        return rootNodes;
    }

    /**
     * 判断是否为根节点
     * 
     * @param parentId 父节点ID
     * @param rootId   指定的根节点ID
     * @param <ID>     ID类型
     * @return 是否为根节点
     */
    private static <ID> boolean isRootNode(ID parentId, ID rootId) {
        if (rootId != null) {
            return Objects.equals(parentId, rootId);
        }
        return parentId == null || (parentId instanceof Number && ((Number) parentId).longValue() == 0);
    }

    /**
     * 树形结构转换为列表（深度优先遍历）
     * 
     * @param treeList 树形结构列表
     * @param <T>      数据类型
     * @param <ID>     ID类型
     * @return 扁平化列表
     */
    public static <T extends TreeNode<ID>, ID> List<T> treeToList(List<T> treeList) {
        List<T> result = new ArrayList<>();
        if (treeList != null && !treeList.isEmpty()) {
            for (T node : treeList) {
                treeToListRecursive(node, result);
            }
        }
        return result;
    }

    /**
     * 递归遍历树节点
     * 
     * @param node   当前节点
     * @param result 结果列表
     * @param <T>    数据类型
     * @param <ID>   ID类型
     */
    private static <T extends TreeNode<ID>, ID> void treeToListRecursive(T node, List<T> result) {
        if (node != null) {
            result.add(node);
            List<T> children = node.getChildren();
            if (children != null && !children.isEmpty()) {
                for (T child : children) {
                    treeToListRecursive(child, result);
                }
            }
        }
    }

    /**
     * 根据ID查找节点
     * 
     * @param treeList    树形结构列表
     * @param targetId    目标ID
     * @param idExtractor ID提取器
     * @param <T>         数据类型
     * @param <ID>        ID类型
     * @return 找到的节点，未找到返回null
     */
    public static <T extends TreeNode<ID>, ID> T findNodeById(List<T> treeList, 
                                                              ID targetId, 
                                                              Function<T, ID> idExtractor) {
        if (treeList == null || treeList.isEmpty() || targetId == null) {
            return null;
        }

        for (T node : treeList) {
            T found = findNodeByIdRecursive(node, targetId, idExtractor);
            if (found != null) {
                return found;
            }
        }
        return null;
    }

    /**
     * 递归查找节点
     * 
     * @param node        当前节点
     * @param targetId    目标ID
     * @param idExtractor ID提取器
     * @param <T>         数据类型
     * @param <ID>        ID类型
     * @return 找到的节点，未找到返回null
     */
    private static <T extends TreeNode<ID>, ID> T findNodeByIdRecursive(T node, 
                                                                        ID targetId, 
                                                                        Function<T, ID> idExtractor) {
        if (node == null) {
            return null;
        }

        if (Objects.equals(idExtractor.apply(node), targetId)) {
            return node;
        }

        List<T> children = node.getChildren();
        if (children != null && !children.isEmpty()) {
            for (T child : children) {
                T found = findNodeByIdRecursive(child, targetId, idExtractor);
                if (found != null) {
                    return found;
                }
            }
        }
        return null;
    }

    /**
     * 获取节点的所有父节点路径
     * 
     * @param treeList     树形结构列表
     * @param targetId     目标节点ID
     * @param idExtractor  ID提取器
     * @param pidExtractor 父ID提取器
     * @param <T>          数据类型
     * @param <ID>         ID类型
     * @return 父节点路径列表（从根节点到目标节点的父节点）
     */
    public static <T extends TreeNode<ID>, ID> List<T> getParentPath(List<T> treeList, 
                                                                     ID targetId, 
                                                                     Function<T, ID> idExtractor, 
                                                                     Function<T, ID> pidExtractor) {
        List<T> allNodes = treeToList(treeList);
        Map<ID, T> nodeMap = allNodes.stream()
                .collect(Collectors.toMap(idExtractor, Function.identity(), (existing, replacement) -> existing));

        List<T> path = new ArrayList<>();
        T targetNode = nodeMap.get(targetId);
        
        if (targetNode != null) {
            buildParentPath(targetNode, nodeMap, pidExtractor, path);
            Collections.reverse(path); // 反转，使路径从根节点开始
        }
        
        return path;
    }

    /**
     * 构建父节点路径
     * 
     * @param node         当前节点
     * @param nodeMap      节点映射
     * @param pidExtractor 父ID提取器
     * @param path         路径列表
     * @param <T>          数据类型
     * @param <ID>         ID类型
     */
    private static <T extends TreeNode<ID>, ID> void buildParentPath(T node, 
                                                                     Map<ID, T> nodeMap, 
                                                                     Function<T, ID> pidExtractor, 
                                                                     List<T> path) {
        if (node != null) {
            ID parentId = pidExtractor.apply(node);
            if (parentId != null) {
                T parent = nodeMap.get(parentId);
                if (parent != null) {
                    path.add(parent);
                    buildParentPath(parent, nodeMap, pidExtractor, path);
                }
            }
        }
    }

    /**
     * 获取节点的所有子节点ID
     * 
     * @param node        根节点
     * @param idExtractor ID提取器
     * @param <T>         数据类型
     * @param <ID>        ID类型
     * @return 所有子节点ID列表
     */
    public static <T extends TreeNode<ID>, ID> List<ID> getAllChildIds(T node, Function<T, ID> idExtractor) {
        List<ID> childIds = new ArrayList<>();
        if (node != null) {
            collectChildIds(node, idExtractor, childIds);
        }
        return childIds;
    }

    /**
     * 收集子节点ID
     * 
     * @param node        当前节点
     * @param idExtractor ID提取器
     * @param childIds    子节点ID列表
     * @param <T>         数据类型
     * @param <ID>        ID类型
     */
    private static <T extends TreeNode<ID>, ID> void collectChildIds(T node, 
                                                                     Function<T, ID> idExtractor, 
                                                                     List<ID> childIds) {
        List<T> children = node.getChildren();
        if (children != null && !children.isEmpty()) {
            for (T child : children) {
                childIds.add(idExtractor.apply(child));
                collectChildIds(child, idExtractor, childIds);
            }
        }
    }

    /**
     * 过滤树节点（保留满足条件的节点及其父节点）
     * 
     * @param treeList  树形结构列表
     * @param predicate 过滤条件
     * @param <T>       数据类型
     * @param <ID>      ID类型
     * @return 过滤后的树形结构
     */
    public static <T extends TreeNode<ID>, ID> List<T> filterTree(List<T> treeList, 
                                                                  java.util.function.Predicate<T> predicate) {
        if (treeList == null || treeList.isEmpty()) {
            return new ArrayList<>();
        }

        List<T> result = new ArrayList<>();
        for (T node : treeList) {
            T filteredNode = filterNodeRecursive(node, predicate);
            if (filteredNode != null) {
                result.add(filteredNode);
            }
        }
        return result;
    }

    /**
     * 递归过滤节点
     * 
     * @param node      当前节点
     * @param predicate 过滤条件
     * @param <T>       数据类型
     * @param <ID>      ID类型
     * @return 过滤后的节点，如果不满足条件且没有满足条件的子节点则返回null
     */
    @SuppressWarnings("unchecked")
    private static <T extends TreeNode<ID>, ID> T filterNodeRecursive(T node, 
                                                                      java.util.function.Predicate<T> predicate) {
        if (node == null) {
            return null;
        }

        // 创建节点副本
        T newNode;
        try {
            newNode = (T) node.getClass().getDeclaredConstructor().newInstance();
            BeanUtils.copyProperties(node, newNode);
            newNode.setChildren(new ArrayList<>());
        } catch (Exception e) {
            log.error("创建节点副本失败: {}", e.getMessage());
            return null;
        }

        // 递归过滤子节点
        List<T> children = node.getChildren();
        boolean hasValidChild = false;
        if (children != null && !children.isEmpty()) {
            for (T child : children) {
                T filteredChild = filterNodeRecursive(child, predicate);
                if (filteredChild != null) {
                    newNode.addChild(filteredChild);
                    hasValidChild = true;
                }
            }
        }

        // 如果当前节点满足条件或有满足条件的子节点，则保留
        if (predicate.test(node) || hasValidChild) {
            return newNode;
        }

        return null;
    }

    /**
     * 计算树的深度
     * 
     * @param treeList 树形结构列表
     * @param <T>      数据类型
     * @param <ID>     ID类型
     * @return 树的最大深度
     */
    public static <T extends TreeNode<ID>, ID> int getTreeDepth(List<T> treeList) {
        if (treeList == null || treeList.isEmpty()) {
            return 0;
        }

        int maxDepth = 0;
        for (T node : treeList) {
            int depth = getNodeDepth(node, 1);
            maxDepth = Math.max(maxDepth, depth);
        }
        return maxDepth;
    }

    /**
     * 计算节点深度
     * 
     * @param node         当前节点
     * @param currentDepth 当前深度
     * @param <T>          数据类型
     * @param <ID>         ID类型
     * @return 节点的最大深度
     */
    private static <T extends TreeNode<ID>, ID> int getNodeDepth(T node, int currentDepth) {
        if (node == null) {
            return currentDepth - 1;
        }

        List<T> children = node.getChildren();
        if (children == null || children.isEmpty()) {
            return currentDepth;
        }

        int maxChildDepth = currentDepth;
        for (T child : children) {
            int childDepth = getNodeDepth(child, currentDepth + 1);
            maxChildDepth = Math.max(maxChildDepth, childDepth);
        }
        return maxChildDepth;
    }

    /**
     * 排序树节点
     * 
     * @param treeList   树形结构列表
     * @param comparator 比较器
     * @param <T>        数据类型
     * @param <ID>       ID类型
     */
    public static <T extends TreeNode<ID>, ID> void sortTree(List<T> treeList, Comparator<T> comparator) {
        if (treeList == null || treeList.isEmpty() || comparator == null) {
            return;
        }

        // 排序当前层级
        treeList.sort(comparator);

        // 递归排序子节点
        for (T node : treeList) {
            List<T> children = node.getChildren();
            if (children != null && !children.isEmpty()) {
                sortTree(children, comparator);
            }
        }
    }

    /**
     * 树节点接口
     * 
     * @param <ID> ID类型
     */
    public interface TreeNode<ID> {
        
        /**
         * 获取节点ID
         * 
         * @return 节点ID
         */
        ID getId();
        
        /**
         * 获取父节点ID
         * 
         * @return 父节点ID
         */
        ID getParentId();
        
        /**
         * 获取子节点列表
         * 
         * @return 子节点列表
         */
        <T extends TreeNode<ID>> List<T> getChildren();
        
        /**
         * 设置子节点列表
         * 
         * @param children 子节点列表
         */
        <T extends TreeNode<ID>> void setChildren(List<T> children);
        
        /**
         * 添加子节点
         * 
         * @param child 子节点
         */
        <T extends TreeNode<ID>> void addChild(T child);
    }

    /**
     * 树形结构构建器
     * 
     * @param <T>  数据类型
     * @param <ID> ID类型
     */
    public static class TreeBuilder<T extends TreeNode<ID>, ID> {
        private List<T> dataList;
        private Function<T, ID> idExtractor;
        private Function<T, ID> pidExtractor;
        private ID rootId;
        private Comparator<T> comparator;
        private java.util.function.Predicate<T> filter;

        public TreeBuilder(List<T> dataList) {
            this.dataList = dataList;
        }

        public TreeBuilder<T, ID> idExtractor(Function<T, ID> idExtractor) {
            this.idExtractor = idExtractor;
            return this;
        }

        public TreeBuilder<T, ID> pidExtractor(Function<T, ID> pidExtractor) {
            this.pidExtractor = pidExtractor;
            return this;
        }

        public TreeBuilder<T, ID> rootId(ID rootId) {
            this.rootId = rootId;
            return this;
        }

        public TreeBuilder<T, ID> sort(Comparator<T> comparator) {
            this.comparator = comparator;
            return this;
        }

        public TreeBuilder<T, ID> filter(java.util.function.Predicate<T> filter) {
            this.filter = filter;
            return this;
        }

        public List<T> build() {
            if (dataList == null || dataList.isEmpty()) {
                return new ArrayList<>();
            }

            if (idExtractor == null || pidExtractor == null) {
                throw new IllegalArgumentException("ID提取器和父ID提取器不能为空");
            }

            // 构建树形结构
            List<T> tree = TreeUtils.buildTree(dataList, idExtractor, pidExtractor, rootId);

            // 应用过滤器
            if (filter != null) {
                tree = TreeUtils.filterTree(tree, filter);
            }

            // 应用排序
            if (comparator != null) {
                TreeUtils.sortTree(tree, comparator);
            }

            return tree;
        }
    }

    /**
     * 树形结构常量类
     */
    public static class TreeConstants {
        
        // 默认根节点ID
        public static final Long DEFAULT_ROOT_ID = 0L;
        public static final String DEFAULT_ROOT_ID_STR = "0";
        
        // 树形结构配置
        public static final int MAX_TREE_DEPTH = 10; // 最大树深度
        public static final int MAX_CHILDREN_COUNT = 1000; // 最大子节点数量
        
        private TreeConstants() {
            // 私有构造函数，防止实例化
        }
    }
}